﻿/* 17. *** Write a program that reads three integer numbers N, K and S 
 * and an array of N elements from the console. 
 * Find in the array a subset of K elements that have sum S or indicate about its absence. */

using System;
using System.Text;
using System.Collections.Generic;

public class SubsetWithGivenLengthAndSum
{
    public static int n;
    public static int k;
    public static List<double> array = new List<double>();
    public static double sum;
    public static List<int> elements = new List<int>();
    public static bool found = false;

    public static void Main()
    {
        if (DataInput())
            FirstGoodCombination(elements, k);
        else
            Console.WriteLine("\nSome of conditions N and K are naturals and K <= N are not complied\n");
    }

    public static bool DataInput()
    {
        Console.Write("\nThe length of array: N = ");
        n = int.Parse(Console.ReadLine());
        if (0 < n)
        {
            Console.WriteLine();
            for (int i = 0; i < n; i++)
            {
                Console.Write("Array[{0}] = ", i);
                array.Add(double.Parse(Console.ReadLine()));
                elements.Add(i + 1);
            }
        }
        else
            return false;

        Console.Write("\nThe length of subset: K = ");
        k = int.Parse(Console.ReadLine());
        if ((k <= 0) || (n < k))
            return false;

        Console.Write("\nSum: S = ");
        sum = double.Parse(Console.ReadLine());

        return true;
    }

    static void FirstGoodCombination(List<int> elements, int k)
    {
        double currentSum;
        int members = elements.Count;
        int ones = 0;
        StringBuilder combination = new StringBuilder(members);
        for (int i = 0; i < members; i++)
            combination.Append("0");

        do
        {
            if (ones == k)
            {
                currentSum = 0;
                for (int j = members - 1; j >= 0; j--)
                    if (combination[j] == '1')
                        currentSum += array[n - elements[j]];

                if (currentSum == sum)
                {
                    found = true;
                    PrintGoodSubset(combination.ToString());
                    break;
                }
            }

            if (combination[members - 1] == '0')
            {
                combination[members - 1] = '1';
                ones++;
            }
            else if (ones == members)
                break;
            else
            {
                combination[members - 1] = '0';
                for (int i = members - 2; i >= 0; i--)
                {
                    if (combination[i] == '0')
                    {
                        combination[i] = '1';
                        break;
                    }
                    else
                    {
                        combination[i] = '0';
                        ones--;
                    }
                }
            }
        } while (ones <= members);

        if (!found)
            PrintGoodSubset("");
    }

    public static void PrintGoodSubset(string twine)
    {
        if (found)
        {
            Console.Write("\nOne of all {0}-length subsets with sum {1} is\n{2} ", k, sum, "{");

            for (int j = twine.Length - 1; j >= 0; j--)
                if (twine[j] == '1')
                {
                    Console.Write("{0}", array[n - elements[j]]);
                    for (int g = j - 1; g >= 0; g--)
                        if (twine[g] == '1')
                            Console.Write(", {0}", array[n - elements[g]]);

                    break;
                }

            Console.WriteLine(" {0}\n", "}");
        }
        else
            Console.WriteLine("\nThere is no such subset!\n");
    }
}